1. Field of the Invention
The present invention relates to a route calculation device and a navigation apparatus for calculating a recommended route leading to a destination. The present invention further relates to a computer readable medium for a route calculation device or a navigation apparatus.
2. Description of Related Art
Navigation systems are widely used. A typical navigation system calculates a recommended route between the present location and a destination, and guides a user along the calculated recommended route by outputting voice or displaying images.
There is known a navigation apparatus that can accept entry of via-points and search for a recommended route leading to a destination through the via-points. In this type of navigation apparatus, a user can arrange the via-points one-by-one to set a desired order of the via-points to be passed through in a recommended route. For simplicity, an order of via-points to be passed through in a route is also referred to hereinafter as a via-point order.
Japanese Patent No. 3482917 discloses a method for a navigation apparatus to automatically set the via-point order that minimizes a traveling time or a traveling distance. In this case, a user does not necessarily re-arrange the via-point order by himself or herself and can let the navigation apparatus automatically obtain the via-point order that enables the user to travel through the via-points as in a short time as possible.
The inventor of the present application has however discovered that the below-described difficulty can arise in connection with the above-described navigation apparatus. When a navigation apparatus arranges the multiple via-points in the via-point order that minimizes route cost, it is required to repeatedly perform route search using cost calculation a lot of times. The number of times the route search is performed corresponds to the number of combinations of all of the via-points, as shown in FIG. 9. Thus, the calculation takes an enormous amount of time. The above difficulty becomes more notable as the number of via-points becomes larger.